660F - Bear and Bowling 4 - CodeForces Solution

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

const int maxn = 2*1e5+5;
long long n,a[maxn];
long long dp[maxn],pref[maxn];
long long ans;

void read()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    reverse(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        dp[i] = dp[i-1] + (a[i]*(n-i+1));
        pref[i] = pref[i-1] + a[i];
    }
}

long long cost(int l, int r)
{
    long long nz = dp[r] - dp[l-1];
    nz -= (pref[r]-pref[l-1])*(n-r);
    return nz;
}

void divide(int l, int r, int optl, int optr)
{
    if(l>r) return;
    int mid = (l+r)/2;
    pair<long long, int> best = {-1000000000000000000,-1};
    for(int i=optl;i<=min(mid,optr);i++)
    {
        long long pom = cost(i,mid);
        if(pom>best.first) best = {pom,i};
    }
    //cout << best.first << " " << mid << endl;
    ans = max(ans,best.first);
    int opt = best.second;
    divide(l,mid-1,optl,opt);
    divide(mid+1,r,opt,optr);
}
void solve()
{
    divide(1,n,1,n);
    cout << ans << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
	solve();
return 0;
}
/*
5
10 -3 -3 8 2
*/